#pragma once

#include  "iostream"
#include "unordered_set"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

//264. 丑数 II
//提示
//        中等
//1K
//相关企业
//        给你一个整数 n ，请你找出并返回第 n 个 丑数 。
//
//丑数 就是只包含质因数 2、3 和/或 5 的正整数。
//
//
//
//示例 1：
//
//输入：n = 10
//输出：12
//解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
//示例 2：
//
//输入：n = 1
//输出：1
//解释：1 通常被视为丑数。
/*
  todo 丑数一定是通过乘2、3、5得到的，当我们得到这样一串丑数 1, 2, 3, 4, 5, 6, 8, 9, 10, 12，想知道下一个丑数的话，暴力方法就是用2、3、5分别把每一个数都乘一遍，拿到第一个比 12 大的就好。*/

int nthUglyNumber(int n) {

    constexpr int arr[] = {2, 3, 5};
    priority_queue<long, vector<long>, greater<long>> queue;
    unordered_set<long> st;
    st.insert(1);
    queue.push(1);
    int ret = 0;
    for (int i = 0; i < n; ++i) {

        auto item = queue.top();
        ret = item;
        queue.pop();

        for (int j = 0; j < 3; ++j) {
            long temp = arr[j] * item;
            if (st.find(temp) == st.end()) {
                st.insert(temp);
                queue.push(temp);
            }

        }


    }

    return ret;

}